//////////////////////////////////////////////////////////////////////////////////////////////////////
// 项目名   : Algorithm
// 文件名   : ModificationSequenceAlgorithm.h
// 作者     : Aiye
// 日期     : 2025/9/9 02:57
// 邮箱     : 2878548868@qq.com
// 摘要     : 介绍修改序列算法
//////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef ALGORITHM_MODIFICATIONSEQUENCEALGORITHM_H
#define ALGORITHM_MODIFICATIONSEQUENCEALGORITHM_H
#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#include <iterator>
#include <list>
#include <random>
#include <vector>
#include <bits/parse_numbers.h>

/**
 * @brief 修改序列
 */
class ModificationSequenceAlgorithm
{
public:
    /**
     * @brief 复制算法
     */
    static void Copy()
    {
        std::vector<int> nVecSrc{1,2,3,4,5};
        decltype(nVecSrc) nVecDst{};
        nVecDst.reserve(nVecSrc.size()); // 预留分配空间
        std::copy(nVecSrc.begin() , nVecSrc.end() , nVecDst.begin()); // 需要预留空间，不会自动扩展目标容器
        std::cout << "vector:" << std::endl;
        print(nVecSrc,nVecDst);

        std::list<int> nListSrc{nVecSrc.begin() , nVecSrc.end()};
        decltype(nListSrc) nListDst{};
        // 使用back_inseter扩展目标容器
        std::copy(nListSrc.begin() , nListSrc.end() , std::back_inserter(nListDst));
        std::cout << "list:" << std::endl;
        print(nListSrc,nListDst);

        std::cout << "Source vecrtor:";
        std::copy(nVecSrc.begin() , nVecSrc.end() , std::ostream_iterator<int>(std::cout , " "));
        std::cout << std::endl;

        std::set<int> nSetSrc{nVecSrc.begin(),nVecSrc.end()};
        decltype(nSetSrc) nSetDst{}; // set没有push_back方法
        std::copy_if(nSetSrc.begin() , nSetSrc.end() , std::inserter(nSetDst,nSetDst.end()),[](auto var)
        {
           return var % 2 == 0;
        });
        std::cout << "Set:" << std::endl;
        print(nSetSrc , nSetDst);
    }

    static void Transform()
    {
        std::vector<int> nVec1{1,2,3,4,5};
        std::vector<int> nVec2(nVec1.size()); // 构造一个相同大小的向量

        std::transform(nVec1.begin() , nVec1.end() , nVec2.begin() , [](auto var)
            {
                return static_cast<int>(std::pow(var , 2));
            }); // 取平方数
        print(nVec1 , nVec2);

        std::string strText1{"hello world"};
        std::string strText2{};
        std::transform(strText1.begin() , strText1.end() , std::back_inserter(strText2) ,[](auto var)
        {
            return std::toupper(var);
        });
        print(strText1, strText2);

        std::vector<int> nResult{};
        std::transform(nVec1.begin() , nVec1.end(),nVec2.begin(),std::back_inserter(nResult),[](auto var1 ,auto var2)
        {
           return var1 + var2;
        });
        print(nVec1 , nVec2 ,nResult);
    }

    /**
     * @brief 介绍填充
     */
    void static Fill()
    {
        std::vector<int> nVec(5); // 大小为5
        print(nVec);
        std::fill(nVec.begin() , nVec.end() ,5);
        print(nVec);

        std::list<int> nList{};
        nList.resize(10);
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<> dis(0,99);
        std::generate(nList.begin() ,nList.end() , [&]()
        {
            return dis(gen);
        });
        print(nList);
    }

    /**
     * @brief 介绍删除
     */
    static void Delete()
    {
        std::vector<int> nVec{1,2,3,4,5,6,7,8,9,10};
        auto nVecit = std::remove(nVec.begin() , nVec.end() , 2); // 删除2
        print(nVec); // 不是真正的删除元素而是将不需要的元素前移动覆盖元素，配合erase实现真正的
        nVec.erase(nVecit , nVec.end());

        auto nVeccit = std::ranges::remove_if(nVec , [](auto var)
        {
            return var % 2 == 0;
        });
        nVec.erase(nVeccit.begin() , nVeccit.end());
        print(nVec);

        std::list<int> nList{1,1,2,2,3,3,4,4,5,5};
        auto nListit = std::unique(nList.begin() , nList.end()); // 移除相邻元素
        auto nList2{nList};
        nList.erase(nListit , nList.end());
        print(nList2 , nList);
    }

    /**
     * @brief 介绍排序
     */
    static void Sort()
    {
        std::vector<int> nVec{5, 2, 8, 1, 9, 3, 7, 4, 6}; // 无序的数组
        std::deque<int> nDeque{nVec.begin() , nVec.end()};
        print(nVec);
        std::sort(nVec.begin() , nVec.end()); // 默认升序，只适应随机访问的容器
        print(nVec);

        print(nDeque);
        std::ranges::sort(nDeque , std::greater<int>());
        print(nDeque);

        std::vector<Person> people{{"Aiye",21,89 } ,{"Bob" , 23 , 98} , {"Alice" , 23 ,100},
            {"Eve" , 22 , 89 } , {"David" , 25 ,100}}; // 自定义结构体
        print(people);

        std::stable_sort(people.begin() , people.end() , [](const Person& var1 , const Person& var2)
        {
           return var1.nScore > var2.nScore;
        }); // 按分数从高到低脾排序，stable不会改变相同数字的顺序
        print(people);
        std::ranges::stable_sort(people , [](const Person& var1 , const Person var2 )
        {
            return var1.nAge < var2.nAge; // 按降序排序
        });
        print(people);
    }

    /**
     * @brief 基于二分查找，事先需要排好序
     */
    static void Find()
    {
        std::vector<int> nVec{1,2,3,4,4,5,63,23,4,6,12,5,34,7,2,5,3,9};
        std::ranges::sort(nVec , std::less<decltype(nVec)::value_type>()); // 默认按照升序进行查找
        auto low = std::lower_bound(nVec.begin() , nVec.end() ,4); // 二分查找
        std::vector<int> nResult1{low , nVec.end()};
        print(nVec , nResult1);

        std::ranges::sort(nVec , std::greater<decltype(nVec)::value_type>()); // 按降序进行排序
        auto up = std::ranges::upper_bound(nVec, 4 , std::greater<decltype(nVec)::value_type>());
        std::vector<int> nResult2{nVec.begin(), up };
        print(nVec , nResult2);
    }

/**
     * @brief 介绍合并操作
     */
    static void Merge()
    {
        std::vector<int> nVec1{1,3,5,7,9};
        std::vector<int> nVec2{0,2,4,6,8};
        std::vector<int> nResult{};

        std::merge(nVec1.begin() , nVec1.end() , nVec2.begin() , nVec2.end() , std::back_inserter(nResult)); // 合并两个排序好的算法
        print(nVec1 , nVec2 , nResult);

        std::list<int> nList1{nVec1.begin() , nVec1.end()};
        std::list<int> nList2{nResult.begin() , nResult.end()};
        std::list<int> nLResult{};
        std::ranges::merge(nList1 , nList2 , std::back_inserter(nLResult));
    }

    /**
     * @brief 堆操作
     */
    static void Heap()
    {
        std::vector<int> nVec{3,1,4,1,5,9,2,6};
        print(nVec);
        std::ranges::make_heap(nVec); // 转化为最大堆
        print(nVec); // 第一个元素是最大值，完全二叉树

        // 添加新元素
        nVec.push_back(7);
        std::ranges::push_heap(nVec); // 添加新元素
        print(nVec);

        // 移除新元素
        std::ranges::pop_heap(nVec);
        print(nVec);
        nVec.pop_back(); // 移除末尾元素
        print(nVec);

        // 堆排序
        std::ranges::sort(nVec);
        print(nVec);
    }

private:
/**
     * @brief 打印容器数据
     * @param containers 容器
     */
    static void print(const auto&... containers)
    {
        (void)std::initializer_list<int>
            {
                ([&]
                    {
                    std::cout << "[container] ";
                    for (const auto& elm : containers)
                    {
                        std::cout << elm << " ";
                    }

                    std::cout << std::endl;
                    return 0;
                }())...
            };
    }; // 打印容器中的内容

    struct Person
    {
        std::string strName{}; // 姓名
        int nAge{};            // 年龄
        int nScore{};          // 分数

        Person(std::string str , int age , int score)
            :strName(str) , nAge(age), nScore(score)
        {}

        friend std::ostream& operator << (std::ostream& os , const Person& person)
        {
            os << "Name:" << person.strName << " "
               << "Age:"  << person.nAge    << " "
               << "Score:"<< person.nScore  << std::endl;
            return os;
        }
    };
};


#endif //ALGORITHM_MODIFICATIONSEQUENCEALGORITHM_H